package leetcode.postOrder2;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 两个栈
 * push 的时候先遍历右子树再遍历左子树，在 pop 的时候才能先访问左子树再访问右子树，这样才符合后序遍历的规则。
 */
public class Solution {

    //青蛙跳台阶   可以跳1 或者2个台阶
    public int JumpFloor(int n) {
        if (n <= 2)
            return n;
        int pre2 = 1, pre1 = 2;
        int result = 1;
        for (int i = 2; i < n; i++) {
            result = pre2 + pre1;
            pre2 = pre1;
            pre1 = result;
        }
        return result;
    }




    // 斐波那契额数列，计算的值只和前两个数据有关，只需要缓存前两个数据即可。
    public int Fibonacci(int n) {
        if(n <=1) {
            return  n;
        }
        int pre2 = 0, pre1 = 1;
        int res = 0;
        for (int i=2;i<=n;i++) {
            res = pre2 + pre1;
            pre2 = pre1;
            pre1 = res;
        }
        return res;
    }


    //两个栈实现一个队列
    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();


    public  void push(Integer elem) {
        in.push(elem);
    }

    public  Integer pop(Integer elem) {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        if (out.isEmpty()){
            System.out.println("队列为空");
            return -1;
        }
        return  out.pop();

    }
    //两个栈实现一个队列


    public static void main(String[] args) {
        StringBuffer str = new StringBuffer("A B");
        System.out.println(replaceSpace(str));
    }


    //空格替换成%20
    public static String replaceSpace(StringBuffer str) {
        int P1 = str.length() - 1;
        for (int i = 0; i <= P1; i++)
            if (str.charAt(i) == ' ')
                str.append("  ");

        int P2 = str.length() - 1;
        while (P1 >= 0 && P2 > P1) {
            char c = str.charAt(P1--);
            if (c == ' ') {
                str.setCharAt(P2--, '0');
                str.setCharAt(P2--, '2');
                str.setCharAt(P2--, '%');
            } else {
                str.setCharAt(P2--, c);
            }
        }
        return str.toString();
    }

    public static void postOrder(Node root) {
        Stack<Node> stack = new Stack<>();
        Stack<Node> output = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                stack.push(node);
                node = node.right;
            }else {
                node = stack.pop();
                node = node.left;
            }
        }
        while (output.size() > 0) {
            Node n = output.pop();
            System.out.print(n.val + "\t");
        }
    }

    static class Node {
        int val;
        Node left;
        Node right;
    }

// 逆向输出链表数据
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 头插法构建逆序链表
        ListNode head = new ListNode(-1);
        while (listNode != null) {
            ListNode temp = listNode.next;
            listNode.next = head.next;
            head.next = listNode;
            listNode = temp;
        }
        // 构建 ArrayList
        ArrayList<Integer> ret = new ArrayList<>();
        head = head.next;
        while (head != null) {
            ret.add(head.val);
            head = head.next;
        }
        return ret;
    }
    static class ListNode {
        ListNode(int val) {
            val = val;
        }
        int val;
        ListNode next;
    }
}
